\begin{lemma}
  Для любой категории $\DD$ существует подкатегория $\FF(\CC)$ такая,
  что $\forall (x\xrightarrow{f} y)\in \MorCC\quad \FF(x)\xrightarrow{f} \FF(y)$.
  % TODO wtf???
\end{lemma}

\begin{definition}
  Функтор $\FF\colon \CC\rightsquigarrow \DD$ называют
  \textit{вложением}\index{Вложение},
  если $\FF_1$ инъективно
  \footnote{Т.е. $\forall x,y\in \ObCC\quad x\ne y\;\Rightarrow\; \FF(x)\ne \FF(y)$}.
\end{definition}

\begin{lemma}
  $\FF$ --- вложение $\Leftrightarrow$ $\FF_1$ задаёт изоморфизм на свой образ.
\end{lemma}

\begin{proof}
  ($\Rightarrow$) Пусть $\FF\colon \CC\rightsquigarrow\DD$. Введём новый функтор:
  $\FF_-\colon \CC\rightsquigarrow \FF[\CC]$. Отображение $\FF_-$
  инъективно и сюрьективно на морфизмах, а значит оно является изофунктором.

  ($\Leftarrow$) Очевидно по определению.
\end{proof}

\begin{theorem}[Кэли] Введём моноид:~~~%, называемой <<симметрической группой>>:
  % Вроде если бы это было симметрической группой, утверждение оказалось
  % бы не верным
  $\mathrm{Sym}(X)\leftrightharpoons(X^X, \circ, 1_X)$.

  Тогда $(G,\bullet,e)$ вкладывается в $\mathrm{Sym}(G)$.
\end{theorem}

\begin{proof}
  Введём $\varphi\colon G\rightarrow \mathrm{Sym}(G)$ следующим образом:
    $$ \varphi(g)\colon a \mapsto a\bullet g $$
  
  Это и будет искомым вложением.
\end{proof}

\begin{theorem}
  Всякая малая категория $\CC$ вложима в $\SET$.
\end{theorem}

\begin{proof}
  Построим $\FF\colon\CC\rightsquigarrow\SET$.
    $$\FF(A)\leftrightharpoons \bigcup\limits_{X\in \ObCC}\CC(X,A)$$
    $$\FF(\alpha)\colon \FF(A)\rightarrow \FF(B)$$
    $$\FF(\alpha)\colon f\mapsto f\circ\alpha$$

  % TODO доказательство выглядит непоследовательно
  Проверяем свойство $\FF(\alpha\circ\beta)=\FF(\alpha)\circ \FF(\beta)$:

   {\begin{tikzcd}
      X \arrow{d}[swap]{f} \arrow{dr}[description]{f\circ\alpha}
        \arrow{drr}{(f\circ\alpha)\circ\beta=f\circ(\alpha\circ\beta)}\\
      A\arrow{r}[swap]{\alpha} & B\arrow{r}[swap]{\beta} & C
    \end{tikzcd}}
\end{proof}

\begin{category} (\textit{Категория всех малых категорий})
  
  Введём категорию $\CAT$:
    $$\Ob\CAT \leftrightharpoons \text{все малые категории}$$
    $$\Mor\CAT \leftrightharpoons \{\FF\mid \FF\colon\CC\rightsquigarrow \DD\}~
               \text{(функторы на $\Ob\CAT$)}$$
    $$1_{\CC}\colon \CC\rightsquigarrow\CC~ \text{(тождественный функтор)}$$
\end{category}

\begin{exercise}Проверить, что $\CAT$ --- действительно категория.\end{exercise}

\begin{lemma}
  Изострелки в $\CAT$ --- изоморфизмы категорий.
\end{lemma}

\begin{exercise}Доказать лемму.\end{exercise}

\begin{category}(\textit{Алгебраические категории}\index{Алгебраическая категория})

  Пусть задана сигнатура
  $\Omega=(\mathrm{Pr},\mathrm{Fn},\mathrm{Const},\nu)$, % TODO большое nu
  где
    $$\mathrm{Pr} \text{--- множество предикатов}$$
    $$\mathrm{Fn} \text{--- множество функциональных символов}$$
    $$\mathrm{Const} \text{--- множество констант}$$
    $$\nu\colon \mathrm{Pr}\cup\mathrm{Fn}\to\NN \text{--- валентность}$$
  
  Валентность задаёт число операндов предиката или функционального символа.

  $\Omega$\textit{-структурой}\index{$\Omega$-структура}
  (или \textit{алгебраической системой}\index{Алгебраическая система})
  будем называть пару $(D,J)$ такую, что $D\ne \emptyset$ и
    $$J(P^n)\colon D^n\to\{0,1\}~~~ \text{(или $J(P^n)\subseteq D^n$)}$$
    $$J(f^n)\colon D^n\to D$$
    $$F(c)\in D$$

  Введём алгебраическую категорию $\OmegaALG=\CC$:
    $$\ObCC\leftrightharpoons\text{множество $\Omega$-структур}$$
    \begin{align*}
      \MorCC\leftrightharpoons \{\alpha\mid
           &(D_1,J_1)\xrightarrow{\alpha}(D_2,J_2) \text{, т.е.}\\
           &\alpha\colon D_1\to D_2\\
           &\alpha(J_1(c))=J_2(c)\\
           &\alpha(J_1(f)(a_1,\ldots,a_n))=J_2(f)(\alpha(a_1),\ldots,\alpha(a_n))\\
           &J_1(P)(a_1,\ldots,a_n)=J_2(P)(\alpha(a_1),\dots,\alpha(a_n))\}
    \end{align*}
\end{category}

\begin{note}
  Тут дано не совсем стандартное определение морфизмов. \\Обычно в последней
  строке не точное равенство, а лишь следствие:
  $$J_1(P)(a_1,\ldots,a_n)\Rightarrow J_2(P)(\alpha(a_1),\dots,\alpha(a_n))$$
  Это нужно не забывать учитывать при решении задач.
\end{note}

\begin{exercise}Доказать, что стрелка $1_D\colon(D,J)\to(D,J)$.\end{exercise}
\begin{exercise}Доказать, что композиция морфизмов --- морфизм.\end{exercise}

\begin{lemma}
  Пусть $\Omega$ не содержит предикатных символов.
  Тогда $\alpha$ --- изострелка в $\OmegaALG \Leftrightarrow$
  $\alpha$ --- биективный морфизм.
\end{lemma}

\begin{exercise}Доказать лемму.\end{exercise}

Введём несколько конкретных алгебраических категорий:

\begin{category}(\textit{Категория моноидов}\index{Категория моноидов})
  
  $$\Omega=\{\mathrm{Pr}=\emptyset, \mathrm{Fn}=\{\circ\},
             \mathrm{Const}=\{e\}\}$$
  $$MON\leftrightharpoons \OmegaALG$$
\end{category}

\begin{category}\textit{Категория колец}\index{Категория колец}: $\RING$
\end{category}

\begin{category}\textit{Категория групп}\index{Категория групп}: $\GROUP$
\end{category}

\begin{note}
  Категория групп не зависит от выбора сигнатуры из следующих вариантов:
    $$(G,\circ), (G,\circ,e), (G,\circ,-^{-1},e)$$
  т.к. если $f\colon G\to H$ сохраняет умножение, то он сохраняет и единичный
  элемент, и обратный. Это не верно для категории $\MON$, т.е. если взять
  сигнатуру $(\{\circ\},\emptyset,\emptyset)$, то получится другая категория.
\end{note}

\begin{proposition}
  $\MON$ вложима в $\CAT$
\end{proposition}

\begin{proof}
    Построим функтор $\Cat\colon \MON\rightsquigarrow \CAT$.
    Вспомним про категорию \ref{monoidascat}, которую мы обозначали
    как $\Cat(G,\bullet,e)$, эта категория и будет значением
    функтора $\Cat$ на объектах.

    {\begin{tikzcd}
      \MON & \CAT \\
      \Cat\colon (G,\bullet,e) \arrow[mapsto]{r} \arrow{d}[swap]{\alpha}
              & \Cat(G,\bullet,e) \arrow[squiggly]{d}{\Cat(\alpha)} \\
      \Cat\colon (H,\bullet',e') \arrow[mapsto]{r}
              & \Cat(H,\bullet',e')
    \end{tikzcd}}

    Теперь мы должны построить $\Cat(\alpha)$.
    Это должен быть некоторый функтор категории $\Cat(G,\bullet,e)$ на
    категорию $\Cat(H,\bullet',e')$. На объектах его построить легко,
    т.к. каждая из этих категорий имеет по одному элементу:
      $$ \Cat(\alpha)(\star_G)\leftrightharpoons \star_H$$

    Теперь определим функтор на морфизмах:
      $$ \Cat(\alpha)(g) \leftrightharpoons \alpha(g)$$

    Проверим, что это действительно функтор.
      $$ \Cat(\alpha)(1_{\star_G})=\alpha(1_{\star_G})=1_{\star_H}$$
      $$ \Cat(\alpha)(g\circ f)=\alpha(g\bullet f)=\alpha(g)\bullet \alpha(f)
                               =\Cat(\alpha)(g)\circ \Cat(\alpha)(f)$$
\end{proof}

\begin{category}
  Пусть $(W,R)$ и $(W',R')$ --- два квазипорядка.
  Отображение $\alpha\colon W\to W'$ будем называть
  морфизмом этих квазипорядков, если
    $$\forall x,y\in W\quad xRy\Rightarrow \alpha(x)R'\alpha(y)$$

  Категорию, в которой объектами являются казвазипорядки,
  а морфизмами --- все морфизмы этих квазипорядков,
  будем обозначать $\QOSET$.
\end{category}

\begin{proposition}
  $\QOSET$ вложима в $\CAT$.
\end{proposition}

\begin{proof}
  Снова будем строить функтор $\Cat\colon \QOSET\rightsquigarrow \CAT$.
  На объектах он будет принимать значения $\Cat(W,R)$,
  см. категорию \ref{quasiascat}.

    {\begin{tikzcd}
      \QOSET & \CAT \\
      \Cat\colon (W,R) \arrow[mapsto]{r} \arrow{d}[swap]{\alpha}
              & \Cat(W,R) \arrow{d}{\Cat(\alpha)} \\
      \Cat\colon (W',R') \arrow[mapsto]{r}
              & \Cat(W',R')
    \end{tikzcd}}

   Теперь зададим $\Cat(\alpha)$. Это должен быть некоторый функтор,
   поэтому задаём его на объектах и мофризмах:
     $$\Cat(\alpha)(x)\leftrightharpoons \alpha(x)$$
     $$\Cat(\alpha)((x,y))\leftrightharpoons (\alpha(x),\alpha(y))$$
   
  Такое определение корректно, потому что если
  $(x,y)\in R$, то по определению морфизмов квазипорядка
  $(\alpha(x),\alpha(y))\in R'$. Доказать, что $\Cat(\alpha)$
  действительно является функтором, остаётся читателю в качестве упражнения.
\end{proof}

\begin{definition} \textit{Конусы} \index{Конус}
  (или \textit{источники}\index{Источник})
  над $(A,B)$, где $A,B\in \ObCC$, --- это упорядоченные
  тройки $(X,\alpha,\beta)$, где $X\xrightarrow{\alpha} A$,
                             $X\xrightarrow{\beta} B$.

  \textit{Категория конусов}\index{Категория конусов}
  над $(A,B)$ обозначается $\Con_{\CC}(A,B)$, морфизмами в ней
  являются такие морфизмы $\gamma\colon X\to Y$, что

    {\begin{tikzcd}
      & X \arrow{ldd}[swap]{\alpha}
          \arrow{d}[description]{\gamma}
          \arrow{rdd}{\beta} \\
      & Y \arrow{ld}{\alpha'}
          \arrow{rd}[swap]{\beta'} \\
      A && B
    \end{tikzcd}}
    $\left\{
        \begin{aligned}
          \gamma\circ\alpha'=\alpha\\
          \gamma\circ\beta'=\beta\\
        \end{aligned}
      \right.
    $
\end{definition}

\begin{definition} \textit{Произведение}\index{Произведение}
  объектов $A$ и $B$ --- финальный объект категории $\Con_{\CC}(A,B)$.
  Произведения будем обозначать так: $(A\times B, p_A, p_B)$.
\end{definition}
